package 题目集.动态规划.最长公共子串;

import org.junit.Test;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/distinct-subsequences/description/
 */
public class 不同的子序列 {
    /**
     * 寻找s中有多少个t的子序列
     * 错误思路分析：
     *      1.滑动窗口：无法确定窗口固定的条件。no
     *      2.字符串哈希：因为涉及到取舍，如果使用字符串哈希，其实也是重新计算，所以不适用。no
     * 动态规划思路：
     *      问题：s[0~n]中有多少个t[0~m]的子序列。（这里的n和m要-1）
     *      当不要s[n]的字符时，问题为：s[0~n-1]中有多少个t[0~m]的子序列。
     *      当要s[n]的字符时，首先得满足s[n]==t[m]。其问题为：s[0~n-1]中有多少个t[0~m-1]的子序列+不要s[n]的情况。
     *      可以不要t[m]吗？不可以，因为问题是以包含t[m]个数为前提的。
     * 方法1：朴素dp
     */
    public int numDistinct1(String s, String t) {
        int m = t.length();
        int n = s.length();
        int[][] dp = new int[m + 1][n + 1];
        Arrays.fill(dp[0], 1); //t为空串时，s的子序列个数为1
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[j][i] = dp[j][i - 1];
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[j][i] += dp[j - 1][i - 1];
                    dp[j][i] %= mod;
                }
            }
        }
        return dp[m][n];
    }

    static int mod = 1000000007;

    /**
     * 状态压缩：每个点依赖于上面和左上的点，所以可以压缩为一维数组。
     */
    public int numDistinct(String s, String t) {
        int m = t.length();
        int n = s.length();
        int[] dp = new int[m + 1];
        dp[0] = 1; //t为空串时，s的子序列个数为1
        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= 1; j--) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[j] += dp[j - 1];
                    dp[j] %= mod;
                }
            }
        }
        return dp[m];
    }

    @Test
    public void test() {
        System.out.println(numDistinct("babgbag", "bag"));
    }
}
